1. Field of the Invention
The present invention relates generally to disk array storage subsystems, and more particularly to a parity assist circuit having integral scatter-gather list processing features useful in such a subsystem
2. Description of Related Art
Modem mass storage subsystems continue to provide increased storage capabilities to fulfill user demands from host computer applications. Due to this critical reliance on large capacity mass storage, demands for enhanced reliability are also high. Various storage device configurations and geometries are commonly applied to meet the demands for higher storage capacity while maintaining or enhancing reliability of the mass storage subsystem.
A popular solution to these mass storage demands for increased capacity and reliability is the use of multiple smaller storage modules configured in geometries that permit redundancy of stored data to assure data integrity in case of various failures. These systems also frequently configure the array of smaller disk drives to enhance storage subsystem performance.
A redundant array of inexpensive (or independent) disks, commonly referred to as RAID, is a collection of disk drives which appears as a single (or virtual) large disk drive to a host computer. Part of the disk storage capacity is typically used to store redundant information about user data stored on the remainder of the storage capacity. This redundant information allows the disk array to continue functioning without the loss of data should an array disk drive member fail, and permits the regeneration of data to a replacement array disk drive member.
Several RAID disk array design alternatives were presented by David A. Patterson et al. in an article entitled A Case for Redundant Arrays of Inexpensive Disks (RAID), University of California Report No. UCB/CSD 87/391, December 1987. This article discusses improvements in performance, reliability, power consumption and scalability that disk arrays provide over single large magnetic disk drives, as well as five disk array arrangements known as RAID levels 1-5.
RAID level 1 comprises N data disks for storing data and N additional mirror disks for storing copies of the information written to the data disks. RAID level 1 write functions require that data be written to two disks, the second mirror disk receiving redundant information, i.e., the same information provided to the data disk. When data is read, it can be read from either disk.
RAID level 2 protects data using a Hamming code. However, RAID level 2 is seldom used largely because it requires special features not found in standard disk drives.
RAID level 3 comprises N+1 disks in which N disks are used to store data and the additional disk is used to store redundant information, i.e., parity information. During RAID level 3 write functions, each block of data is divided into N portions for storing among the N data disks. The corresponding parity information is calculated from the data written to the N data disks and is written to a dedicated parity disk. When data is read, all N data disks must be accessed. The parity disk is used to reconstruct the data in the event of disk failure.
RAID level 4 also comprises N+1 disks in which N disks are used to store data and the additional disk is used to store parity information. RAID level 4 differs from RAID level 3 in that data to be saved is divided into blocks, and each block is stored on a single one of the data disks. Writes still require access to two disks, i.e., one of the N data disks and the parity disk. In a similar fashion, read operations typically need only access a single one of the N data disks unless the data to be read exceeds the block length stored on each disk. As with RAID level 3, the parity disk is used to reconstruct information in the event of disk failure.
RAID level 5 is similar to RAID level 4 except that parity information, in addition to the data, is distributed across the N+1 disks. Thus, each disk includes some blocks for storing data and some blocks for storing parity information. Where parity information is stored is controlled by an algorithm implemented by the user. RAID level 5 differs from RAID level 4 in that the parity information is distributed across the disks rather than concentrated on one, which provides the opportunity to perform concurrent write operations.
RAID levels 0 and 6 were defined after the Patterson et al. article. RAID level 0 involves disk striping without data protection. Disk striping distributes data across multiple disk drives to permit parallel operations. Strictly speaking, the absence of redundancy makes the term RAID a misnomer, however RAID level 0 is commonly used interchangeably with disk stripping. RAID level 6 expands upon RAID levels 4 and 5 by providing N+2 disks in which N disks are used to store data and 2 disks are used to store two independently computed sets of parity information.
RAID levels 3-6 have become collectively known as parity RAID. The data stored in the subsystem is logically divided into stripes each subdivided into smaller units often referred to as “blocks.” A stripe is comprised of a group of related data blocks and a corresponding redundancy (i.e., parity) block (or blocks in RAID level 6 ). The parity data is calculated by determining the exclusive-OR (XOR) product of the associated data blocks. Advantageously, if one of the data blocks contains an error it can be reconstructed by calculating the XOR product of the remaining data blocks and the parity block. For instance, the XOR product of the second, third and fourth data blocks and the parity block is equal to the data in the first data block. Thus any missing or unavailable data block (or parity block) may be reconstructed from the remaining available blocks of any particular stripe.
RAID storage subsystems typically utilize a controller that shields the host computer from the details of managing the redundant array. In particular, the RAID controller typically performs all the above-identified parity computations with no intervention by, or even knowledge of the host system. The controller makes the subsystem appear to the host computer as one (or more) highly reliable, high capacity disk drive. Unbeknownst to the host system, the RAID controller distributes the host computer's data across numerous small independent disk drives with redundancy and error checking so as to improve subsystem reliability and/or performance. The RAID controller typically employs a central processing unit (CPU) and program memory that stores instructions for the CPU. RAID controllers also frequently provide cache memory to further improve performance. The cache memory is associated with the controller such that the storage blocks on the disk array are mapped to blocks in the cache memory. This mapping is transparent to the host computer. The host computer simply requests blocks of data to be read or written and the RAID controller manipulates the disk array and cache memory as required.
Posting the cached data to the disk drives is often done by a read-modify-write (RMW) method wherein the new data blocks to be posted are used in conjunction with the associated old data blocks and old parity data on the disk drives to compute the new parity data, as mentioned above. A second posting method, called the full write method (also referred to as a stripe write method or simply a stripe write) writes new data blocks and associated new parity data without reading the old data blocks or old parity data from the disk drives. Rather, all data blocks which comprise a stripe are resident in the cache memory, the new parity data is calculated therefrom, and the new data blocks and new parity block are written to the disk drives.
It is long known in the art that the CPU of the RAID controller can compute the XOR parity data as it reads and writes data from and to the disk drives (or as it receives data from the host systems). The CPU in a modern, high performance RAID controller has a number of responsibilities and can often be overloaded by its many computational functions. RAID controllers often also include a parity assist circuit for providing the XOR operations during parity calculations. Although the CPU could perform this function, the parity assist circuit relieves the CPU of this burden. For example, when the CPU determines that an XOR product is needed, it gives a short series of instructions to the parity assist circuit. These instructions typically include the address and length of a first operand, the address and length of a second operand, and the destination address and length for the result. In response to these instructions, the parity assist circuit obtains the first and second operands from the cache memory of the RAID controller, calculates the XOR product, and stores the XOR product at the destination address in the cache memory. In the meantime, the CPU may continue on to other operations while awaiting an interrupt from the parity assist circuit to signify that the XOR calculation is complete. As a result, the parity assist circuit saves the CPU a substantial amount of processing time.
Although the parity assist circuit helps speed the RAID storage subsystem, considerable room for improvement exists. For example, each time the CPU requests an XOR calculation from the parity assist circuit, the CPU generates a short series of setup instructions to compute a particular parity block from two source blocks. Each parity block computation therefore consumes CPU processing time to setup the computation parameters and start the parity assist circuit operating. Furthermore, each time the parity assist circuit completes an XOR calculation and generates an interrupt, the CPU halts the current operation and implements an interrupt routine. This typically involves saving CPU state information on a stack, executing an interrupt operation, then reloading the stored state information to resume the previous operation. Since XOR parity calculations are so prevalent in RAID storage subsystems, the high volume of CPU setup instructions to the parity assist circuit and subsequent interrupts by the parity assist circuit is a key performance factor.
Accordingly, a need exists for a parity assist circuit in RAID storage subsystems that reduces demands on processor overhead and improves performance.